class TreeNode():
    def __init__(self,val=0,left=None,right=None):
        self.val=val 
        self.left=left 
        self.right=right

from collections import deque
def build_level(lst):
    root=TreeNode(lst[0])
    que=deque([root])
    i=1 
    while len(que)>0 and i<len(lst):
        cur=que.popleft()
        if lst[i]: 
            cur.left=TreeNode(lst[i])
            que.append(cur.left)
        if i+1<len(lst) and lst[i+1]:
            cur.right=TreeNode(lst[i+1])
            que.append(cur.right)
        i+=2 
    return root 

def solve(root):
    if not root: return
    cur=root 
    while cur:
        if cur.left: #**
            l,pre=cur.left,cur.left
            while pre.right: pre=pre.right 
            pre.right=cur.right 
            cur.right=l
            cur.left=None
        cur=cur.right #***
    return root 

def traversal(root,ans):
    if not root: 
        ans.append(None)
        return 
    ans.append(root.val)
    traversal(root.left,ans)
    traversal(root.right,ans)

def out(root):
    ans=[]
    traversal(root,ans)
    return ans 

root=build_level([1,2,5,3,4,None,6])
print(out(solve(root)))


    

